#include <gtest/gtest.h>

using namespace ::std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target);
};

// nums为无重复元素的生序排列数组
// 暴力求解
// int Solution::searchInsert(vector<int>& nums, int target) {
// 	int index = 0;
// 	// 考虑数组越界啊
// 	while(index < nums.size() && nums[index] < target) index++;
// 	return index;
// }

// 二分查找
int Solution::searchInsert(vector<int>& nums, int target) {
	int size = nums.size();
	int mid, left = 0, right = size - 1;
	while(left <= right) {
		mid = (left + right) / 2;
		if(nums[mid] == target) return mid;
		else if(nums[mid] > target) right = mid - 1;
		else left = mid + 1;
	}
	return nums[mid] > target ? mid : mid + 1;
}

class SearchInsertCheck : public ::testing::Test {
public:
	class Solution solution;
	vector<int> nums = {1,3,5,6};
	// vector<int> nums({1,3,5,6}); // 会报错，为什么
};

TEST_F(SearchInsertCheck, testSearchInsert_1) {
	int target = 5;
	EXPECT_TRUE(2 == solution.searchInsert(nums, target));
}

TEST_F(SearchInsertCheck, testSearchInsert_2) {
	int target = 2;
	EXPECT_TRUE(1 == solution.searchInsert(nums, target));
}

TEST_F(SearchInsertCheck, testSearchInsert_3) {
	int target = 7; // 本机测，越界没有报错，LeetCode越界会报错
	EXPECT_TRUE(4 == solution.searchInsert(nums, target));
}

TEST_F(SearchInsertCheck, testSearchInsert_4) {
	vector<int> nums({1});
	int target = 0;
	EXPECT_TRUE(0 == solution.searchInsert(nums, target));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
